package org.hot100_1;

import org.algorithm.List.ListNode;

public class leetcode34 {
    public ListNode mergeKLists(ListNode[] lists) {

        ListNode ans = null;

        for (int i = 0; i < lists.length; i++) {
            ans = mergeTwoList(ans,lists[i]);
        }

        return ans;
    }

    private ListNode mergeTwoList(ListNode list1,ListNode list2){
        if (list1==null || list2==null){
            return list1==null ? list2 :list1;
        }

        ListNode dummy = new ListNode(-1);
        ListNode merged = dummy;

        while (list1!=null && list2!=null){
            if (list1.val<list2.val){
                merged.next=list1;
                list1=list1.next;
            }else {
                merged.next=list2;
                list2=list2.next;
            }
            merged=merged.next;
        }

        if (list1==null){
            merged.next=list2;
        }
        if (list2==null){
            merged.next=list1;
        }

        return dummy.next;

    }
}
